`
https://leetcode.cn/problems/find-duplicate-subtrees/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function (root) {
  // 记录所有子树出现的次数
  const memo = new Map()
  // 返回列表
  const res = []

  // 将子树序列化为字符串，通过对比字符串是否相同就可以判断子树是否的重复的
  function serialize(node) {
    // 用 '#' 表示空结点
    if (node === null) {
      return '#'
    }

    // 递归获取左右子树的序列化结果
    const left = serialize(node.left)
    const right = serialize(node.right)

    // 由于需要获取子树的结果，所以对子树的处理要放在后序位置
    const str = `${left},${right},${node.val}`

    // 获取序列的出现次数
    const freq = memo.get(str) || 0

    // 如果是第一次重复出现，则加入结果
    if (freq === 1) {
      res.push(node)
    }

    // 更新序列出现的频率
    memo.set(str, freq + 1)

    // 返回本子树的序列化结果
    return str
  }

  // 寻找重复的子树
  serialize(root)

  // 返回结果
  return res
};